Regression

Linear regression

This chapter contains the Appendix for the chapter on regression analysis.

In order to understand the coefficients in the multiple regression we can derive them separately. We have already seen that in the univariate case:

\[ \hat{\beta_1}=\frac{COV_{XY}}{s_x^2} \]

We have also seen that we can isolate the partial effect of a single variable in a multiple regression. Specifically, we can calculate the coefficient of the i-th variable as

\[ \hat{\beta_{i}} = {COV(\tilde{Y_{i}}, \tilde{X_{i}}) \over V(\tilde{X_i})} \]

where \(\tilde{Y_{i}}\) is the residual from the regression of \(Y\) on all variables except for the i-th and \(\tilde{X_i}\) is the residual from the regression of \(X_i\) on all other variables. Let’s illustrate this with an example.

x1 <- rnorm(100, 5, 15)
x2 <- rnorm(100, 20, 10) + 3*x1

y <- 50 + 2*x1 + 7*x2 + rnorm(100, 0, 5)

We have added some randomness through the rnorm command so the coefficients are not exactly as we set them but close. Clearly x1 and x2 have partial influence on y.

mod <- lm(y~x1+x2)
summary(mod)

Call:
lm(formula = y ~ x1 + x2)

Residuals:
     Min       1Q   Median       3Q      Max 
-11.1613  -2.6256   0.3265   3.0405  14.8474 

Coefficients:
            Estimate Std. Error t value Pr(>|t|)    
(Intercept) 50.48353    0.97811   51.61   <2e-16 ***
x1           2.18488    0.12423   17.59   <2e-16 ***
x2           6.95716    0.04083  170.37   <2e-16 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 4.62 on 97 degrees of freedom
Multiple R-squared:  0.9998,    Adjusted R-squared:  0.9998 
F-statistic: 2.623e+05 on 2 and 97 DF,  p-value: < 2.2e-16

To see the partial effect of x1 we run regressions for x1 on x2, as well as y on x2 and obtain the residuals \(\tilde{x1}\) and \(\tilde{x2}\). Notice that x1 is highly correlated with x2.

regX1 <- lm(x1~x2)  
summary(regX1)

Call:
lm(formula = x1 ~ x2)

Residuals:
    Min      1Q  Median      3Q     Max 
-8.0614 -2.6574 -0.5356  2.4341  8.1637 

Coefficients:
             Estimate Std. Error t value Pr(>|t|)    
(Intercept) -6.108735   0.501794  -12.17   <2e-16 ***
x2           0.317513   0.008592   36.95   <2e-16 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 3.757 on 98 degrees of freedom
Multiple R-squared:  0.933, Adjusted R-squared:  0.9324 
F-statistic:  1365 on 1 and 98 DF,  p-value: < 2.2e-16
tildeX1 <- residuals(regX1)
regY1 <- lm(y~x2)
tildeY1 <- residuals(regY1)

We can use the residuals to create the partial plots as seen above.

# This is the same as avPlot
ggplot(data.frame(y = tildeY1, x = tildeX1), aes(x = x, y = y)) +
  geom_point(shape = 1) +
  geom_smooth(method = 'lm', se = FALSE, color = "red") +
  labs(y = "y | others", x = "x1 | others") + 
  theme_bw()

avPlots(mod)

And the regression of the residuals of y on x1 yields the same coefficient as in the original regression (minus the rounding errors).

# This is the same coefficient as in the original regression 
summary(lm(tildeY1~tildeX1 - 1)) # -1 since we want no intercept

Call:
lm(formula = tildeY1 ~ tildeX1 - 1)

Residuals:
     Min       1Q   Median       3Q      Max 
-11.1613  -2.6256   0.3265   3.0405  14.8474 

Coefficients:
        Estimate Std. Error t value Pr(>|t|)    
tildeX1    2.185      0.123   17.77   <2e-16 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 4.573 on 99 degrees of freedom
Multiple R-squared:  0.7613,    Adjusted R-squared:  0.7589 
F-statistic: 315.7 on 1 and 99 DF,  p-value: < 2.2e-16
print("Coefficient using the partial covariance:")
[1] "Coefficient using the partial covariance:"
cov(tildeY1, tildeX1)/var(tildeX1)
[1] 2.184883

Logistic regression

Maximum likelihood estimation

For non-linear models we cannot turn to linear algebra to solve for the unknown parameters. However, we can use a statistical method called maximum likelihood estimation (MLE). Given observed data and an assumption about their distribution we can estimate for which parameter values the observed data is most likely to occur. We do this by calculating the joint log likelihood of the observations given a choice of parameters (more on that below). Next, we change our parameter values a little bit and see if the joint log likelihood improved. We keep doing that until we cannot find better parameter values anymore (that is we have reached the maximum likelihood). In the following example we have a histogram of a data set which we assume to be normally distributed. You can now try to find the best parameter values by changing the mean and the variance. Recall that the normal distribution is fully described by just those two parameters. In each step the log likelihood is automatically calculated. The maximum likelihood so far is shown as the high score and the line in the lower graph shows the development of the log likelihood for the past couple of tries.

Estimation of the parameters \(\beta_i\)

Let’s return to the model to figure out how the parameters \(\beta_i\) are estimated. In the data we observe the \(y_i\), the outcome variable that is either \(0\) or \(1\), and the \(x_{i,j}\), the predictors for each observation. In addition, by using the logit model we have assumed the following functional form.

\[ P(y_i = 1) = \frac{1}{1 + e^{-(\beta_0 + \beta_1 * x_{1,i} + \beta_2 * x_{2,i} + ... +\beta_m * x_{m,i})}} \]

So far we have looked at estimating the \(\beta_i\) with R but have not discussed how that works. In contrast to linear models (e.g. OLS) we cannot rely on linear algebra to solve for \(\beta_i\) since the function is now non-linear. Therefore, we turn to a methodology called maximum likelihood estimation. Basically, we try out different \(\beta_i\) and choose the combination that best its the observed data. In other words: choose the combination of \(\beta_i\) that maximize the likelihood of observing the given data set. For each individual we have information about the binary outcome and the predictors. For those whose outcome is \(1\) we want to choose the \(\beta_i\) such that our predicted probability of the outcome (\(P(y_i = 1)\)) is as close to \(1\) as possible. At the same time, for those whose outcome is \(0\) we would like the prediction (\(P(y_i = 1)\)) to be as close to \(0\) as possible. Therefore, we “split” the sample into two groups (outcome \(1\) and outcome \(0\)). For the first group each individual has the probability function shown above which we want to maximize for this group. For the other group we would need to minimize the joint probability since we want our prediction to be as close to \(0\) as possible. Alternatively we can easily transform the probability to \(P(y_i = 0)\) which we can then maximize. Since probabilities add up to \(1\) and we only have two possible outcomes \(P(y_i = 0) = 1 - P(y_i = 1)\). This is convenient because now we can calculate the joint likelihood of all observations and maximize a single function. We assume that the observations are independent from each other and thus the joint likelihood is just the product of the individual probabilities. Thus for the group of \(n_1\) individuals with outcome \(1\) we have the joint likelihood

\[ \prod_{i=1}^{n_1} {1 \over 1 + e^{-(\beta_0 + \beta_1 * x_{1,i} + \beta_2 * x_{2,i} + ... +\beta_m * x_{m,i})}} \]

For the second group of \(n_2\) individuals with outcome \(0\) we get the joint likelihood

\[ \prod_{j=1}^{n_{2}} 1 - {1 \over 1 + e^{-(\beta_0 + \beta_1 * x_{1,i} + \beta_2 * x_{2,i} + ... +\beta_m * x_{m,i})}} \]

In order to find the optimal \(\beta_i\) we need to combine to two groups into one joint likelihood function for all observations. We can once again do that by multiplying them with each other. However, now we need to add an indicator in order to determine in which group the observation is.

\[ \prod_{k = 1}^{n_1 + n_2} \left({1 \over 1 + e^{-(\beta_0 + \beta_1 * x_{1,i} + \beta_2 * x_{2,i} + ... +\beta_m * x_{m,i})}}\right)^{y_i} \times \left( 1 - {1 \over 1 + e^{-(\beta_0 + \beta_1 * x_{1,i} + \beta_2 * x_{2,i} + ... +\beta_m * x_{m,i})}}\right)^{1-y_i} \]

The indicators \((\cdot)^{y_i}\) and \((\cdot)^{1-y_i}\) select the appropriate likelihood. To illustrate this consider an individual with outcome \(y_j = 1\)

\[ \begin{align*} &\left({1 \over 1 + e^{-(\beta_0 + \beta_1 * x_{1,j} + \beta_2 * x_{2,j} + ... +\beta_m * x_{m,j})}}\right)^{y_j} \times \left( 1 - {1 \over 1 + e^{-(\beta_0 + \beta_1 * x_{1,j} + \beta_2 * x_{2,j} + ... +\beta_m * x_{m,j})}}\right)^{1-y_j}\\ =&\left({1 \over 1 + e^{-(\beta_0 + \beta_1 * x_{1,j} + \beta_2 * x_{2,j} + ... +\beta_m * x_{m,j})}}\right)^{1} \times \left( 1 - {1 \over 1 + e^{-(\beta_0 + \beta_1 * x_{1,j} + \beta_2 * x_{2,j} + ... +\beta_m * x_{m,j})}}\right)^{0}\\ =&{1 \over 1 + e^{-(\beta_0 + \beta_1 * x_{1,j} + \beta_2 * x_{2,j} + ... +\beta_m * x_{m,j})}} \times 1\\ =&{1 \over 1 + e^{-(\beta_0 + \beta_1 * x_{1,j} + \beta_2 * x_{2,j} + ... +\beta_m * x_{m,j})}} \end{align*} \]

Equivalently for an individual with outcome \(y_s = 0\):

\[ \begin{align*} &\left({1 \over 1 + e^{-(\beta_0 + \beta_1 * x_{1,i} + \beta_2 * x_{2,i} + ... +\beta_m * x_{m,i})}}\right)^{y_i} \times \left( 1 - {1 \over 1 + e^{-(\beta_0 + \beta_1 * x_{1,i} + \beta_2 * x_{2,i} + ... +\beta_m * x_{m,i})}}\right)^{1-y_i}\\ =&\left({1 \over 1 + e^{-(\beta_0 + \beta_1 * x_{1,j} + \beta_2 * x_{2,j} + ... +\beta_m * x_{m,j})}}\right)^{0} \times \left( 1 - {1 \over 1 + e^{-(\beta_0 + \beta_1 * x_{1,j} + \beta_2 * x_{2,j} + ... +\beta_m * x_{m,j})}}\right)^{1}\\ =&1\times \left( 1 - {1 \over 1 + e^{-(\beta_0 + \beta_1 * x_{1,j} + \beta_2 * x_{2,j} + ... +\beta_m * x_{m,j})}}\right)^{1}\\ =& 1 - {1 \over 1 + e^{-(\beta_0 + \beta_1 * x_{1,j} + \beta_2 * x_{2,j} + ... +\beta_m * x_{m,j})}} \end{align*} \]

Example

Consider an experiment in which we want to find out whether a person will listen to the full song or skip it. Further, assume that the genre of the song is the only determining factor of whether somebody is likely to skip it or not. Each individual has rated the genre on a scale from 1 (worst) to 10 (best). Our model looks as follows:

\[ P(\text{skipped}_i) = {1 \over 1 + e^{-(\beta_0 + \beta_1 \text{rating}_i)}} \]

The probability that individual \(i\) will skip a song is the logistic function with \(X = \beta_0 + \beta_1 * \text{rating}_i\), where \(\text{rating}_i\) is individual \(i\)’s rating of the genre of the song. Since we assume independence of individuals we can write the joint likelihood as

\[ \prod_{i=1}^{N} \left({1 \over 1 + e^{-(\beta_0 + \beta_1 \text{rating}_i)}}\right)^{y_i} \times \left(1- {1 \over 1 + e^{-(\beta_0 + \beta_1 \text{rating}_i)}}\right)^{(1-y_i)} \]

Notice that \(y_i\) is either equal to one or to zero. So for each individual only one of the two parts is not equal to one (recall that any real number to the power of 0 is equal to 1). The the part left of the plus sign is “looking at” individuals who skipped the song given their rating and the right part is looking at individuals who did not skip the song given their rating. For the former we want the predicted probability of skipping to be as high as possible. For the latter we want the predicted probability of not skipping to be as high as possible and thus write \(1 - {1 \over 1+ e^{-(\beta_0 + \beta_1 \text{rating}_i)}}\). This is convenient since we can now maximize a single function. Another way to simplify the calculation and make it computationally feasible is taking the logarithm. This will ensure that extremely small probabilities can still be processed by the computer (see this illustration).

Manually applying this in R would looks as follows. We begin by simulating some data. ratingGenre is a vector of 10000 randomly generated numbers between 1 and 10. pSkip will be a vector of probabilities generated by applying the logistic function to our linear model, with the parameters \(\beta_0 = 1\) and \(\beta_1 = -0.3\).

ratingGenre <- sample(1:10, size = 10000, replace = TRUE)
linModel <- 1 - 0.3 * ratingGenre
pSkip <- 1/(1+exp(-linModel))

Now we have to sample whether a user skipped a song or not, based on their probability of skipping. The resulting vector skipped is composed of 0s and 1s and indicates whether or not a person skipped a song.

skipped <- 1:length(pSkip)
for(i in 1:length(pSkip)){
  skipped[i] <- sample(c(1, 0), size = 1, prob = c(pSkip[i], 1-pSkip[i]))
}

Our simulated data now looks as follows:

The visualization shows that an increase in genreRating leads to a decrease in the probability of a song being skipped. Now we want to perform maximum likelihood estimation and see how close we get to the true parameter values. To achieve this, we need a function that, given a value for \(\beta_0\) and \(\beta_1\), gives us the value of the log likelihood. The following code defines such a function.

mlEstimate <- function(beta_0, beta_1){
  pred <- 1/(1+exp(-(beta_0 + beta_1 * ratingGenre)))
  loglik <- skipped * log(pred) + (1-skipped) * log(1 - pred)
  sum(loglik)
}

The log likelihood function has the following form.

As you can see, the maximum of the log likelihood function lies around -0.3, 1, the true parameter values. Now we need to find an algorithm that finds the combination of \(\beta_0\) and \(\beta_1\) that optimizes this function. There are multiple ways to go about this. The glm() function uses the built-in optimization function optim(). While we could do the same, we will use a slightly different approach to make the process more intuitive. We are going to employ something called grid maximization. Basically, we make a list of all plausible combinations of parameter values and calculate the log likelihood for each combination. Then we simply select the parameter combination that has the highest log likelihood.

prob_beta_0 and prob_beta_1 are now vectors that contain 100 plausible values for each parameter.

rr rr prob_beta_0 <- seq(0.5, 1.5, length.out = 100) prob_beta_1 <- seq(-1, 0, length.out = 100)

LS0tCm91dHB1dDoKICBodG1sX2RvY3VtZW50OgogICAgZGZfcHJpbnQ6IHBhZ2VkCiAgaHRtbF9ub3RlYm9vazogZGVmYXVsdAotLS0KCmBgYHtyLCBpbmNsdWRlPUZBTFNFfQprbml0cjo6b3B0c19jaHVuayRzZXQoZWNobyA9IFRSVUUpCm9wdGlvbnMoZGlnaXRzID0gNykKYGBgCgojIyBSZWdyZXNzaW9uCgojIyMgTGluZWFyIHJlZ3Jlc3Npb24gCgpUaGlzIGNoYXB0ZXIgY29udGFpbnMgdGhlIEFwcGVuZGl4IGZvciB0aGUgY2hhcHRlciBvbiByZWdyZXNzaW9uIGFuYWx5c2lzLgoKSW4gb3JkZXIgdG8gdW5kZXJzdGFuZCB0aGUgY29lZmZpY2llbnRzIGluIHRoZSBtdWx0aXBsZSByZWdyZXNzaW9uIHdlIGNhbiBkZXJpdmUgdGhlbSBzZXBhcmF0ZWx5LiBXZSBoYXZlIGFscmVhZHkgc2VlbiB0aGF0IGluIHRoZSB1bml2YXJpYXRlIGNhc2U6CgokJApcaGF0e1xiZXRhXzF9PVxmcmFje0NPVl97WFl9fXtzX3heMn0KJCQKCldlIGhhdmUgW2Fsc28gc2VlbiB0aGF0IHdlIGNhbiBpc29sYXRlIHRoZSBwYXJ0aWFsIGVmZmVjdF0oI3BhcnRpYWwtcGxvdHMpIG9mIGEgc2luZ2xlIHZhcmlhYmxlIGluIGEgbXVsdGlwbGUgcmVncmVzc2lvbi4gU3BlY2lmaWNhbGx5LCB3ZSBjYW4gY2FsY3VsYXRlIHRoZSBjb2VmZmljaWVudCBvZiB0aGUgaS10aCB2YXJpYWJsZSBhcwoKJCQKXGhhdHtcYmV0YV97aX19ID0ge0NPVihcdGlsZGV7WV97aX19LCBcdGlsZGV7WF97aX19KSBcb3ZlciBWKFx0aWxkZXtYX2l9KX0KJCQKCndoZXJlICRcdGlsZGV7WV97aX19JCBpcyB0aGUgcmVzaWR1YWwgZnJvbSB0aGUgcmVncmVzc2lvbiBvZiAkWSQgb24gYWxsIHZhcmlhYmxlcyBleGNlcHQgZm9yIHRoZSBpLXRoIGFuZCAkXHRpbGRle1hfaX0kIGlzIHRoZSByZXNpZHVhbCBmcm9tIHRoZSByZWdyZXNzaW9uIG9mICRYX2kkIG9uIGFsbCBvdGhlciB2YXJpYWJsZXMuIExldCdzIGlsbHVzdHJhdGUgdGhpcyB3aXRoIGFuIGV4YW1wbGUuCgpgYGB7ciwgZWNobz1UUlVFfQp4MSA8LSBybm9ybSgxMDAsIDUsIDE1KQp4MiA8LSBybm9ybSgxMDAsIDIwLCAxMCkgKyAzKngxCgp5IDwtIDUwICsgMip4MSArIDcqeDIgKyBybm9ybSgxMDAsIDAsIDUpCmBgYAoKV2UgaGF2ZSBhZGRlZCBzb21lIHJhbmRvbW5lc3MgdGhyb3VnaCB0aGUgYGBgcm5vcm1gYGAgY29tbWFuZCBzbyB0aGUgY29lZmZpY2llbnRzIGFyZSBub3QgZXhhY3RseSBhcyB3ZSBzZXQgdGhlbSBidXQgY2xvc2UuIENsZWFybHkgeDEgYW5kIHgyIGhhdmUgcGFydGlhbCBpbmZsdWVuY2Ugb24geS4KCmBgYHtyIH0KbW9kIDwtIGxtKHl+eDEreDIpCnN1bW1hcnkobW9kKQpgYGAKClRvIHNlZSB0aGUgcGFydGlhbCBlZmZlY3Qgb2YgeDEgd2UgcnVuIHJlZ3Jlc3Npb25zIGZvciB4MSBvbiB4MiwgYXMgd2VsbCBhcyB5IG9uIHgyIGFuZCBvYnRhaW4gdGhlIHJlc2lkdWFscyAkXHRpbGRle3gxfSQgYW5kICRcdGlsZGV7eDJ9JC4gTm90aWNlIHRoYXQgeDEgaXMgaGlnaGx5IGNvcnJlbGF0ZWQgd2l0aCB4Mi4gCgpgYGB7ciB9CnJlZ1gxIDwtIGxtKHgxfngyKSAgCnN1bW1hcnkocmVnWDEpCnRpbGRlWDEgPC0gcmVzaWR1YWxzKHJlZ1gxKQpyZWdZMSA8LSBsbSh5fngyKQp0aWxkZVkxIDwtIHJlc2lkdWFscyhyZWdZMSkKYGBgCgpXZSBjYW4gdXNlIHRoZSByZXNpZHVhbHMgdG8gY3JlYXRlIHRoZSBwYXJ0aWFsIHBsb3RzIGFzIHNlZW4gYWJvdmUuCgpgYGB7ciB9CiMgVGhpcyBpcyB0aGUgc2FtZSBhcyBhdlBsb3QKZ2dwbG90KGRhdGEuZnJhbWUoeSA9IHRpbGRlWTEsIHggPSB0aWxkZVgxKSwgYWVzKHggPSB4LCB5ID0geSkpICsKICBnZW9tX3BvaW50KHNoYXBlID0gMSkgKwogIGdlb21fc21vb3RoKG1ldGhvZCA9ICdsbScsIHNlID0gRkFMU0UsIGNvbG9yID0gInJlZCIpICsKICBsYWJzKHkgPSAieSB8IG90aGVycyIsIHggPSAieDEgfCBvdGhlcnMiKSArIAogIHRoZW1lX2J3KCkKYXZQbG90cyhtb2QpCmBgYAoKQW5kIHRoZSByZWdyZXNzaW9uIG9mIHRoZSByZXNpZHVhbHMgb2YgeSBvbiB4MSB5aWVsZHMgdGhlIHNhbWUgY29lZmZpY2llbnQgYXMgaW4gdGhlIG9yaWdpbmFsIHJlZ3Jlc3Npb24gKG1pbnVzIHRoZSByb3VuZGluZyBlcnJvcnMpLiAKCmBgYHtyfQojIFRoaXMgaXMgdGhlIHNhbWUgY29lZmZpY2llbnQgYXMgaW4gdGhlIG9yaWdpbmFsIHJlZ3Jlc3Npb24gCnN1bW1hcnkobG0odGlsZGVZMX50aWxkZVgxIC0gMSkpICMgLTEgc2luY2Ugd2Ugd2FudCBubyBpbnRlcmNlcHQKcHJpbnQoIkNvZWZmaWNpZW50IHVzaW5nIHRoZSBwYXJ0aWFsIGNvdmFyaWFuY2U6IikKY292KHRpbGRlWTEsIHRpbGRlWDEpL3Zhcih0aWxkZVgxKQpgYGAKCgojIyMgTG9naXN0aWMgcmVncmVzc2lvbgoKIyMjIyBNYXhpbXVtIGxpa2VsaWhvb2QgZXN0aW1hdGlvbgoKRm9yIG5vbi1saW5lYXIgbW9kZWxzIHdlIGNhbm5vdCB0dXJuIHRvIGxpbmVhciBhbGdlYnJhIHRvIHNvbHZlIGZvciB0aGUgdW5rbm93biBwYXJhbWV0ZXJzLiBIb3dldmVyLCB3ZSBjYW4gdXNlIGEgc3RhdGlzdGljYWwgbWV0aG9kIGNhbGxlZCBtYXhpbXVtIGxpa2VsaWhvb2QgZXN0aW1hdGlvbiAoTUxFKS4gR2l2ZW4gb2JzZXJ2ZWQgZGF0YSBhbmQgYW4gYXNzdW1wdGlvbiBhYm91dCB0aGVpciBkaXN0cmlidXRpb24gd2UgY2FuIGVzdGltYXRlIGZvciB3aGljaCBwYXJhbWV0ZXIgdmFsdWVzIHRoZSBvYnNlcnZlZCBkYXRhIGlzIG1vc3QgbGlrZWx5IHRvIG9jY3VyLiBXZSBkbyB0aGlzIGJ5IGNhbGN1bGF0aW5nIHRoZSBqb2ludCBsb2cgbGlrZWxpaG9vZCBvZiB0aGUgb2JzZXJ2YXRpb25zIGdpdmVuIF9hXyBjaG9pY2Ugb2YgcGFyYW1ldGVycyAobW9yZSBvbiB0aGF0IGJlbG93KS4gTmV4dCwgd2UgY2hhbmdlIG91ciBwYXJhbWV0ZXIgdmFsdWVzIGEgbGl0dGxlIGJpdCBhbmQgc2VlIGlmIHRoZSBqb2ludCBsb2cgbGlrZWxpaG9vZCBpbXByb3ZlZC4gV2Uga2VlcCBkb2luZyB0aGF0IHVudGlsIHdlIGNhbm5vdCBmaW5kIGJldHRlciBwYXJhbWV0ZXIgdmFsdWVzIGFueW1vcmUgKHRoYXQgaXMgd2UgaGF2ZSByZWFjaGVkIHRoZSBtYXhpbXVtIGxpa2VsaWhvb2QpLiBJbiB0aGUgZm9sbG93aW5nIGV4YW1wbGUgd2UgaGF2ZSBhIGhpc3RvZ3JhbSBvZiBhIGRhdGEgc2V0IHdoaWNoIHdlIGFzc3VtZSB0byBiZSBub3JtYWxseSBkaXN0cmlidXRlZC4gWW91IGNhbiBub3cgdHJ5IHRvIGZpbmQgdGhlIGJlc3QgcGFyYW1ldGVyIHZhbHVlcyBieSBjaGFuZ2luZyB0aGUgbWVhbiBhbmQgdGhlIHZhcmlhbmNlLiBSZWNhbGwgdGhhdCB0aGUgbm9ybWFsIGRpc3RyaWJ1dGlvbiBpcyBmdWxseSBkZXNjcmliZWQgYnkganVzdCB0aG9zZSB0d28gcGFyYW1ldGVycy4gSW4gZWFjaCBzdGVwIHRoZSBsb2cgbGlrZWxpaG9vZCBpcyBhdXRvbWF0aWNhbGx5IGNhbGN1bGF0ZWQuIFRoZSBtYXhpbXVtIGxpa2VsaWhvb2Qgc28gZmFyIGlzIHNob3duIGFzIHRoZSBoaWdoIHNjb3JlIGFuZCB0aGUgbGluZSBpbiB0aGUgbG93ZXIgZ3JhcGggc2hvd3MgdGhlIGRldmVsb3BtZW50IG9mIHRoZSBsb2cgbGlrZWxpaG9vZCBmb3IgdGhlIHBhc3QgY291cGxlIG9mIHRyaWVzLiAgCgo8aWZyYW1lIHNyYz0iaHR0cHM6Ly9sZWFybi53dS5hYy5hdC9zaGlueS9pbXNtL21heExpa2VsaWhvb2QvIiBzdHlsZT0iYm9yZGVyOiBub25lOyB3aWR0aDogODAwcHg7IGhlaWdodDogOTAwcHgiPjwvaWZyYW1lPgoKIyMjIyBFc3RpbWF0aW9uIG9mIHRoZSBwYXJhbWV0ZXJzICRcYmV0YV9pJAoKTGV0J3MgcmV0dXJuIHRvIHRoZSBtb2RlbCB0byBmaWd1cmUgb3V0IGhvdyB0aGUgcGFyYW1ldGVycyAkXGJldGFfaSQgYXJlIGVzdGltYXRlZC4gSW4gdGhlIGRhdGEgd2Ugb2JzZXJ2ZSB0aGUgJHlfaSQsIHRoZSBvdXRjb21lIHZhcmlhYmxlIHRoYXQgaXMgZWl0aGVyICQwJCBvciAkMSQsIGFuZCB0aGUgJHhfe2ksan0kLCB0aGUgcHJlZGljdG9ycyBmb3IgZWFjaCBvYnNlcnZhdGlvbi4gSW4gYWRkaXRpb24sIGJ5IHVzaW5nIHRoZSBsb2dpdCBtb2RlbCB3ZSBoYXZlIGFzc3VtZWQgdGhlIGZvbGxvd2luZyBmdW5jdGlvbmFsIGZvcm0uCgokJApQKHlfaSA9IDEpID0gXGZyYWN7MX17MSArIGVeey0oXGJldGFfMCArIFxiZXRhXzEgKiB4X3sxLGl9ICsgXGJldGFfMiAqIHhfezIsaX0gKyAuLi4gK1xiZXRhX20gKiB4X3ttLGl9KX19CiQkCgpTbyBmYXIgd2UgaGF2ZSBsb29rZWQgYXQgZXN0aW1hdGluZyB0aGUgJFxiZXRhX2kkIHdpdGggUiBidXQgaGF2ZSBub3QgZGlzY3Vzc2VkIGhvdyB0aGF0IHdvcmtzLiBJbiBjb250cmFzdCB0byBsaW5lYXIgbW9kZWxzIChlLmcuIE9MUykgd2UgY2Fubm90IHJlbHkgb24gbGluZWFyIGFsZ2VicmEgdG8gc29sdmUgZm9yICRcYmV0YV9pJCBzaW5jZSB0aGUgZnVuY3Rpb24gaXMgbm93IG5vbi1saW5lYXIuIFRoZXJlZm9yZSwgd2UgdHVybiB0byBhIG1ldGhvZG9sb2d5IGNhbGxlZCBfbWF4aW11bSBsaWtlbGlob29kIGVzdGltYXRpb25fLiBCYXNpY2FsbHksIHdlIHRyeSBvdXQgZGlmZmVyZW50ICRcYmV0YV9pJCBhbmQgY2hvb3NlIHRoZSBjb21iaW5hdGlvbiB0aGF0IGJlc3QgaXRzIHRoZSBvYnNlcnZlZCBkYXRhLiBJbiBvdGhlciB3b3JkczogY2hvb3NlIHRoZSBjb21iaW5hdGlvbiBvZiAkXGJldGFfaSQgdGhhdCBtYXhpbWl6ZSB0aGUgbGlrZWxpaG9vZCBvZiBvYnNlcnZpbmcgdGhlIGdpdmVuIGRhdGEgc2V0LiBGb3IgZWFjaCBpbmRpdmlkdWFsIHdlIGhhdmUgaW5mb3JtYXRpb24gYWJvdXQgdGhlIGJpbmFyeSBvdXRjb21lIGFuZCB0aGUgcHJlZGljdG9ycy4gRm9yIHRob3NlIHdob3NlIG91dGNvbWUgaXMgJDEkIHdlIHdhbnQgdG8gY2hvb3NlIHRoZSAkXGJldGFfaSQgc3VjaCB0aGF0IG91ciBwcmVkaWN0ZWQgcHJvYmFiaWxpdHkgb2YgdGhlIG91dGNvbWUgKCRQKHlfaSA9IDEpJCkgaXMgYXMgY2xvc2UgdG8gJDEkIGFzIHBvc3NpYmxlLiBBdCB0aGUgc2FtZSB0aW1lLCBmb3IgdGhvc2Ugd2hvc2Ugb3V0Y29tZSBpcyAkMCQgd2Ugd291bGQgbGlrZSB0aGUgcHJlZGljdGlvbiAoJFAoeV9pID0gMSkkKSB0byBiZSBhcyBjbG9zZSB0byAkMCQgYXMgcG9zc2libGUuIFRoZXJlZm9yZSwgd2UgInNwbGl0IiB0aGUgc2FtcGxlIGludG8gdHdvIGdyb3VwcyAob3V0Y29tZSAkMSQgYW5kIG91dGNvbWUgJDAkKS4gRm9yIHRoZSBmaXJzdCBncm91cCBlYWNoIGluZGl2aWR1YWwgaGFzIHRoZSBwcm9iYWJpbGl0eSBmdW5jdGlvbiBzaG93biBhYm92ZSB3aGljaCB3ZSB3YW50IHRvIG1heGltaXplIGZvciB0aGlzIGdyb3VwLiBGb3IgdGhlIG90aGVyIGdyb3VwIHdlIHdvdWxkIG5lZWQgdG8gbWluaW1pemUgdGhlIGpvaW50IHByb2JhYmlsaXR5IHNpbmNlIHdlIHdhbnQgb3VyIHByZWRpY3Rpb24gdG8gYmUgYXMgY2xvc2UgdG8gJDAkIGFzIHBvc3NpYmxlLiBBbHRlcm5hdGl2ZWx5IHdlIGNhbiBlYXNpbHkgdHJhbnNmb3JtIHRoZSBwcm9iYWJpbGl0eSB0byAkUCh5X2kgPSAwKSQgd2hpY2ggd2UgY2FuIHRoZW4gbWF4aW1pemUuIFNpbmNlIHByb2JhYmlsaXRpZXMgYWRkIHVwIHRvICQxJCBhbmQgd2Ugb25seSBoYXZlIHR3byBwb3NzaWJsZSBvdXRjb21lcyAkUCh5X2kgPSAwKSA9IDEgLSBQKHlfaSA9IDEpJC4gVGhpcyBpcyBjb252ZW5pZW50IGJlY2F1c2Ugbm93IHdlIGNhbiBjYWxjdWxhdGUgdGhlIGpvaW50IGxpa2VsaWhvb2Qgb2YgYWxsIG9ic2VydmF0aW9ucyBhbmQgbWF4aW1pemUgYSBzaW5nbGUgZnVuY3Rpb24uIFdlIGFzc3VtZSB0aGF0IHRoZSBvYnNlcnZhdGlvbnMgYXJlIGluZGVwZW5kZW50IGZyb20gZWFjaCBvdGhlciBhbmQgdGh1cyB0aGUgam9pbnQgbGlrZWxpaG9vZCBpcyBqdXN0IHRoZSBwcm9kdWN0IG9mIHRoZSBpbmRpdmlkdWFsIHByb2JhYmlsaXRpZXMuIFRodXMgZm9yIHRoZSBncm91cCBvZiAkbl8xJCBpbmRpdmlkdWFscyB3aXRoIG91dGNvbWUgJDEkIHdlIGhhdmUgdGhlIGpvaW50IGxpa2VsaWhvb2QKCiQkClxwcm9kX3tpPTF9XntuXzF9IHsxIFxvdmVyIDEgKyBlXnstKFxiZXRhXzAgKyBcYmV0YV8xICogeF97MSxpfSArIFxiZXRhXzIgKiB4X3syLGl9ICsgLi4uICtcYmV0YV9tICogeF97bSxpfSl9fQokJAoKRm9yIHRoZSBzZWNvbmQgZ3JvdXAgb2YgJG5fMiQgaW5kaXZpZHVhbHMgd2l0aCBvdXRjb21lICQwJCB3ZSBnZXQgdGhlIGpvaW50IGxpa2VsaWhvb2QgCgokJApccHJvZF97aj0xfV57bl97Mn19IDEgLSB7MSBcb3ZlciAxICsgZV57LShcYmV0YV8wICsgXGJldGFfMSAqIHhfezEsaX0gKyBcYmV0YV8yICogeF97MixpfSArIC4uLiArXGJldGFfbSAqIHhfe20saX0pfX0gCiQkCgpJbiBvcmRlciB0byBmaW5kIHRoZSBvcHRpbWFsICRcYmV0YV9pJCB3ZSBuZWVkIHRvIGNvbWJpbmUgdG8gdHdvIGdyb3VwcyBpbnRvIG9uZSBqb2ludCBsaWtlbGlob29kIGZ1bmN0aW9uIGZvciBhbGwgb2JzZXJ2YXRpb25zLiBXZSBjYW4gb25jZSBhZ2FpbiBkbyB0aGF0IGJ5IG11bHRpcGx5aW5nIHRoZW0gd2l0aCBlYWNoIG90aGVyLiBIb3dldmVyLCBub3cgd2UgbmVlZCB0byBhZGQgYW4gaW5kaWNhdG9yIGluIG9yZGVyIHRvIGRldGVybWluZSBpbiB3aGljaCBncm91cCB0aGUgb2JzZXJ2YXRpb24gaXMuCgoKJCQKXHByb2Rfe2sgPSAxfV57bl8xICsgbl8yfSBcbGVmdCh7MSBcb3ZlciAxICsgZV57LShcYmV0YV8wICsgXGJldGFfMSAqIHhfezEsaX0gKyBcYmV0YV8yICogeF97MixpfSArIC4uLiArXGJldGFfbSAqIHhfe20saX0pfX1ccmlnaHQpXnt5X2l9IFx0aW1lcyBcbGVmdCggMSAtIHsxIFxvdmVyIDEgKyBlXnstKFxiZXRhXzAgKyBcYmV0YV8xICogeF97MSxpfSArIFxiZXRhXzIgKiB4X3syLGl9ICsgLi4uICtcYmV0YV9tICogeF97bSxpfSl9fVxyaWdodCleezEteV9pfQokJAoKVGhlIGluZGljYXRvcnMgJChcY2RvdClee3lfaX0kIGFuZCAkKFxjZG90KV57MS15X2l9JCBzZWxlY3QgdGhlIGFwcHJvcHJpYXRlIGxpa2VsaWhvb2QuIFRvIGlsbHVzdHJhdGUgdGhpcyBjb25zaWRlciBhbiBpbmRpdmlkdWFsIHdpdGggb3V0Y29tZSAkeV9qID0gMSQgCgokJApcYmVnaW57YWxpZ24qfQomXGxlZnQoezEgXG92ZXIgMSArIGVeey0oXGJldGFfMCArIFxiZXRhXzEgKiB4X3sxLGp9ICsgXGJldGFfMiAqIHhfezIsan0gKyAuLi4gK1xiZXRhX20gKiB4X3ttLGp9KX19XHJpZ2h0KV57eV9qfSBcdGltZXMgXGxlZnQoIDEgLSB7MSBcb3ZlciAxICsgZV57LShcYmV0YV8wICsgXGJldGFfMSAqIHhfezEsan0gKyBcYmV0YV8yICogeF97MixqfSArIC4uLiArXGJldGFfbSAqIHhfe20san0pfX1ccmlnaHQpXnsxLXlfan1cXAo9JlxsZWZ0KHsxIFxvdmVyIDEgKyBlXnstKFxiZXRhXzAgKyBcYmV0YV8xICogeF97MSxqfSArIFxiZXRhXzIgKiB4X3syLGp9ICsgLi4uICtcYmV0YV9tICogeF97bSxqfSl9fVxyaWdodCleezF9IFx0aW1lcyBcbGVmdCggMSAtIHsxIFxvdmVyIDEgKyBlXnstKFxiZXRhXzAgKyBcYmV0YV8xICogeF97MSxqfSArIFxiZXRhXzIgKiB4X3syLGp9ICsgLi4uICtcYmV0YV9tICogeF97bSxqfSl9fVxyaWdodCleezB9XFwKPSZ7MSBcb3ZlciAxICsgZV57LShcYmV0YV8wICsgXGJldGFfMSAqIHhfezEsan0gKyBcYmV0YV8yICogeF97MixqfSArIC4uLiArXGJldGFfbSAqIHhfe20san0pfX0gXHRpbWVzIDFcXAo9JnsxIFxvdmVyIDEgKyBlXnstKFxiZXRhXzAgKyBcYmV0YV8xICogeF97MSxqfSArIFxiZXRhXzIgKiB4X3syLGp9ICsgLi4uICtcYmV0YV9tICogeF97bSxqfSl9fSAKXGVuZHthbGlnbip9CiQkCgpFcXVpdmFsZW50bHkgZm9yIGFuIGluZGl2aWR1YWwgd2l0aCBvdXRjb21lICR5X3MgPSAwJDoKCiQkClxiZWdpbnthbGlnbip9CiZcbGVmdCh7MSBcb3ZlciAxICsgZV57LShcYmV0YV8wICsgXGJldGFfMSAqIHhfezEsaX0gKyBcYmV0YV8yICogeF97MixpfSArIC4uLiArXGJldGFfbSAqIHhfe20saX0pfX1ccmlnaHQpXnt5X2l9IFx0aW1lcyBcbGVmdCggMSAtIHsxIFxvdmVyIDEgKyBlXnstKFxiZXRhXzAgKyBcYmV0YV8xICogeF97MSxpfSArIFxiZXRhXzIgKiB4X3syLGl9ICsgLi4uICtcYmV0YV9tICogeF97bSxpfSl9fVxyaWdodCleezEteV9pfVxcCj0mXGxlZnQoezEgXG92ZXIgMSArIGVeey0oXGJldGFfMCArIFxiZXRhXzEgKiB4X3sxLGp9ICsgXGJldGFfMiAqIHhfezIsan0gKyAuLi4gK1xiZXRhX20gKiB4X3ttLGp9KX19XHJpZ2h0KV57MH0gXHRpbWVzIFxsZWZ0KCAxIC0gezEgXG92ZXIgMSArIGVeey0oXGJldGFfMCArIFxiZXRhXzEgKiB4X3sxLGp9ICsgXGJldGFfMiAqIHhfezIsan0gKyAuLi4gK1xiZXRhX20gKiB4X3ttLGp9KX19XHJpZ2h0KV57MX1cXAo9JjFcdGltZXMgXGxlZnQoIDEgLSB7MSBcb3ZlciAxICsgZV57LShcYmV0YV8wICsgXGJldGFfMSAqIHhfezEsan0gKyBcYmV0YV8yICogeF97MixqfSArIC4uLiArXGJldGFfbSAqIHhfe20san0pfX1ccmlnaHQpXnsxfVxcCj0mIDEgLSB7MSBcb3ZlciAxICsgZV57LShcYmV0YV8wICsgXGJldGFfMSAqIHhfezEsan0gKyBcYmV0YV8yICogeF97MixqfSArIC4uLiArXGJldGFfbSAqIHhfe20san0pfX0KXGVuZHthbGlnbip9CiQkCgojIyMjIEV4YW1wbGUKCkNvbnNpZGVyIGFuIGV4cGVyaW1lbnQgaW4gd2hpY2ggd2Ugd2FudCB0byBmaW5kIG91dCB3aGV0aGVyIGEgcGVyc29uIHdpbGwgbGlzdGVuIHRvIHRoZSBmdWxsIHNvbmcgb3Igc2tpcCBpdC4gRnVydGhlciwgYXNzdW1lIHRoYXQgdGhlIGdlbnJlIG9mIHRoZSBzb25nIGlzIHRoZSBvbmx5IGRldGVybWluaW5nIGZhY3RvciBvZiB3aGV0aGVyIHNvbWVib2R5IGlzIGxpa2VseSB0byBza2lwIGl0IG9yIG5vdC4gRWFjaCBpbmRpdmlkdWFsIGhhcyByYXRlZCB0aGUgZ2VucmUgb24gYSBzY2FsZSBmcm9tIDEgKHdvcnN0KSB0byAxMCAoYmVzdCkuIE91ciBtb2RlbCBsb29rcyBhcyBmb2xsb3dzOgoKJCQgClAoXHRleHR7c2tpcHBlZH1faSkgPSB7MSBcb3ZlciAxICsgZV57LShcYmV0YV8wICsgXGJldGFfMSBcdGV4dHtyYXRpbmd9X2kpfX0KJCQKClRoZSBwcm9iYWJpbGl0eSB0aGF0IGluZGl2aWR1YWwgJGkkIHdpbGwgc2tpcCBhIHNvbmcgaXMgdGhlIGxvZ2lzdGljIGZ1bmN0aW9uIHdpdGggJFggPSBcYmV0YV8wICsgXGJldGFfMSAqIFx0ZXh0e3JhdGluZ31faSQsIHdoZXJlICRcdGV4dHtyYXRpbmd9X2kkIGlzIGluZGl2aWR1YWwgJGkkJ3MgcmF0aW5nIG9mIHRoZSBnZW5yZSBvZiB0aGUgc29uZy4gU2luY2Ugd2UgYXNzdW1lIGluZGVwZW5kZW5jZSBvZiBpbmRpdmlkdWFscyB3ZSBjYW4gd3JpdGUgdGhlIGpvaW50IGxpa2VsaWhvb2QgYXMKCiQkClxwcm9kX3tpPTF9XntOfSBcbGVmdCh7MSBcb3ZlciAxICsgZV57LShcYmV0YV8wICsgXGJldGFfMSBcdGV4dHtyYXRpbmd9X2kpfX1ccmlnaHQpXnt5X2l9IFx0aW1lcyBcbGVmdCgxLSB7MSBcb3ZlciAxICsgZV57LShcYmV0YV8wICsgXGJldGFfMSBcdGV4dHtyYXRpbmd9X2kpfX1ccmlnaHQpXnsoMS15X2kpfQokJAoKTm90aWNlIHRoYXQgJHlfaSQgaXMgZWl0aGVyIGVxdWFsIHRvIG9uZSBvciB0byB6ZXJvLiBTbyBmb3IgZWFjaCBpbmRpdmlkdWFsIG9ubHkgb25lIG9mIHRoZSB0d28gcGFydHMgaXMgbm90IGVxdWFsIHRvIG9uZSAocmVjYWxsIHRoYXQgYW55IHJlYWwgbnVtYmVyIHRvIHRoZSBwb3dlciBvZiAwIGlzIGVxdWFsIHRvIDEpLiBUaGUgdGhlIHBhcnQgbGVmdCBvZiB0aGUgcGx1cyBzaWduIGlzICJsb29raW5nIGF0IiBpbmRpdmlkdWFscyB3aG8gc2tpcHBlZCB0aGUgc29uZyBnaXZlbiB0aGVpciByYXRpbmcgYW5kIHRoZSByaWdodCBwYXJ0IGlzIGxvb2tpbmcgYXQgaW5kaXZpZHVhbHMgd2hvIGRpZCBub3Qgc2tpcCB0aGUgc29uZyBnaXZlbiB0aGVpciByYXRpbmcuIEZvciB0aGUgZm9ybWVyIHdlIHdhbnQgdGhlIHByZWRpY3RlZCBwcm9iYWJpbGl0eSBvZiBza2lwcGluZyB0byBiZSBhcyBoaWdoIGFzIHBvc3NpYmxlLiBGb3IgdGhlIGxhdHRlciB3ZSB3YW50IHRoZSBwcmVkaWN0ZWQgcHJvYmFiaWxpdHkgb2YgKm5vdCogc2tpcHBpbmcgdG8gYmUgYXMgaGlnaCBhcyBwb3NzaWJsZSBhbmQgdGh1cyB3cml0ZSAkMSAtIHsxIFxvdmVyIDErIGVeey0oXGJldGFfMCArIFxiZXRhXzEgXHRleHR7cmF0aW5nfV9pKX19JC4gVGhpcyBpcyBjb252ZW5pZW50IHNpbmNlIHdlIGNhbiBub3cgbWF4aW1pemUgYSBzaW5nbGUgZnVuY3Rpb24uIEFub3RoZXIgd2F5IHRvIHNpbXBsaWZ5IHRoZSBjYWxjdWxhdGlvbiBhbmQgbWFrZSBpdCBjb21wdXRhdGlvbmFsbHkgZmVhc2libGUgaXMgdGFraW5nIHRoZSBsb2dhcml0aG0uIFRoaXMgd2lsbCBlbnN1cmUgdGhhdCBleHRyZW1lbHkgc21hbGwgcHJvYmFiaWxpdGllcyBjYW4gc3RpbGwgYmUgcHJvY2Vzc2VkIGJ5IHRoZSBjb21wdXRlciAoW3NlZSB0aGlzIGlsbHVzdHJhdGlvbl0oI3N1bS1vZi1sbi12cy1wcm9kdWN0KSkuICAgIApgYGB7ciBlY2hvID0gRkFMU0V9CnNldC5zZWVkKDEyMykKYGBgCgpNYW51YWxseSBhcHBseWluZyB0aGlzIGluIFIgd291bGQgbG9va3MgYXMgZm9sbG93cy4gV2UgYmVnaW4gYnkgc2ltdWxhdGluZyBzb21lIGRhdGEuIGBgYHJhdGluZ0dlbnJlYGBgIGlzIGEgdmVjdG9yIG9mIDEwMDAwIHJhbmRvbWx5IGdlbmVyYXRlZCBudW1iZXJzIGJldHdlZW4gMSBhbmQgMTAuIGBgYHBTa2lwYGBgIHdpbGwgYmUgYSB2ZWN0b3Igb2YgcHJvYmFiaWxpdGllcyBnZW5lcmF0ZWQgYnkgYXBwbHlpbmcgdGhlIGxvZ2lzdGljIGZ1bmN0aW9uIHRvIG91ciBsaW5lYXIgbW9kZWwsIHdpdGggdGhlIHBhcmFtZXRlcnMgJFxiZXRhXzAgPSAxJCBhbmQgJFxiZXRhXzEgPSAtMC4zJC4KCmBgYHtyLCBtZXNzYWdlID0gRkFMU0UsIHdhcm5pbmcgPSBGQUxTRX0KcmF0aW5nR2VucmUgPC0gc2FtcGxlKDE6MTAsIHNpemUgPSAxMDAwMCwgcmVwbGFjZSA9IFRSVUUpCmxpbk1vZGVsIDwtIDEgLSAwLjMgKiByYXRpbmdHZW5yZQpwU2tpcCA8LSAxLygxK2V4cCgtbGluTW9kZWwpKQpgYGAKCk5vdyB3ZSBoYXZlIHRvIHNhbXBsZSB3aGV0aGVyIGEgdXNlciBza2lwcGVkIGEgc29uZyBvciBub3QsIGJhc2VkIG9uIHRoZWlyIHByb2JhYmlsaXR5IG9mIHNraXBwaW5nLiBUaGUgcmVzdWx0aW5nIHZlY3RvciBgYGBza2lwcGVkYGBgIGlzIGNvbXBvc2VkIG9mIDBzIGFuZCAxcyBhbmQgaW5kaWNhdGVzIHdoZXRoZXIgb3Igbm90IGEgcGVyc29uIHNraXBwZWQgYSBzb25nLiAKCmBgYHtyLCBtZXNzYWdlID0gRkFMU0UsIHdhcm5pbmcgPSBGQUxTRX0Kc2tpcHBlZCA8LSAxOmxlbmd0aChwU2tpcCkKZm9yKGkgaW4gMTpsZW5ndGgocFNraXApKXsKICBza2lwcGVkW2ldIDwtIHNhbXBsZShjKDEsIDApLCBzaXplID0gMSwgcHJvYiA9IGMocFNraXBbaV0sIDEtcFNraXBbaV0pKQp9CmBgYAoKT3VyIHNpbXVsYXRlZCBkYXRhIG5vdyBsb29rcyBhcyBmb2xsb3dzOgoKYGBge3IsIGVjaG8gPSBGQUxTRSwgZmlnLmFsaWduPSJjZW50ZXIiLCBmaWcuY2FwPSJQZXJjZW50IG9mIHNvbmdzIHNraXBwZWQgYXMgYSBmdW5jdGlvbiBvZiB0aGUgZ2VucmUgcmF0aW5nIn0KZnJlcSA8LSBwcm9wLnRhYmxlKHRhYmxlKGRhdGEuZnJhbWUoc2tpcHBlZCA9IHNraXBwZWQsIHJhdGluZyA9IHJhdGluZ0dlbnJlKSksIG1hcmdpbiA9IDIpICogMTAwCgpmcmVxIDwtIGFzLmRhdGEuZnJhbWUoZnJlcSkKCmNvbG5hbWVzKGZyZXEpIDwtIGMoIlNraXBwZWQiLCAicmF0aW5nIiwgIkZyZXEiKQoKZnJlcSRTa2lwcGVkIDwtIGZhY3RvcihmcmVxJFNraXBwZWQsIGxldmVscyA9IGMoMCwxKSwgbGFiZWxzID0gYygiTm8iLCAiWWVzIikpCgpnZ3Bsb3QoZGF0YSA9IGZyZXEsIGFlcyh4ID0gcmF0aW5nLCB5ID0gRnJlcSwgZmlsbCA9IFNraXBwZWQpKSArCmdlb21fY29sKCkgKwogIHlsYWIoIlBlcmNlbnQiKSArIAogIHhsYWIoIkdlbnJlIHJhdGluZyIpICsKICB0aGVtZV9idygpCgpgYGAKClRoZSB2aXN1YWxpemF0aW9uIHNob3dzIHRoYXQgYW4gaW5jcmVhc2UgaW4gYGBgZ2VucmVSYXRpbmdgYGAgbGVhZHMgdG8gYSBkZWNyZWFzZSBpbiB0aGUgcHJvYmFiaWxpdHkgb2YgYSBzb25nIGJlaW5nIHNraXBwZWQuIE5vdyB3ZSB3YW50IHRvIHBlcmZvcm0gbWF4aW11bSBsaWtlbGlob29kIGVzdGltYXRpb24gYW5kIHNlZSBob3cgY2xvc2Ugd2UgZ2V0IHRvIHRoZSB0cnVlIHBhcmFtZXRlciB2YWx1ZXMuIFRvIGFjaGlldmUgdGhpcywgd2UgbmVlZCBhIGZ1bmN0aW9uIHRoYXQsIGdpdmVuIGEgdmFsdWUgZm9yICRcYmV0YV8wJCBhbmQgJFxiZXRhXzEkLCBnaXZlcyB1cyB0aGUgdmFsdWUgb2YgdGhlIGxvZyBsaWtlbGlob29kLiBUaGUgZm9sbG93aW5nIGNvZGUgZGVmaW5lcyBzdWNoIGEgZnVuY3Rpb24uCgpgYGB7ciwgbWVzc2FnZSA9IEZBTFNFLCB3YXJuaW5nID0gRkFMU0V9Cm1sRXN0aW1hdGUgPC0gZnVuY3Rpb24oYmV0YV8wLCBiZXRhXzEpewogIHByZWQgPC0gMS8oMStleHAoLShiZXRhXzAgKyBiZXRhXzEgKiByYXRpbmdHZW5yZSkpKQogIGxvZ2xpayA8LSBza2lwcGVkICogbG9nKHByZWQpICsgKDEtc2tpcHBlZCkgKiBsb2coMSAtIHByZWQpCiAgc3VtKGxvZ2xpaykKfQpgYGAKClRoZSBsb2cgbGlrZWxpaG9vZCBmdW5jdGlvbiBoYXMgdGhlIGZvbGxvd2luZyBmb3JtLgoKYGBge3IsIGVjaG8gPSBGQUxTRSwgZmlnLmNhcD0iUGxvdCBvZiB0aGUgbG9nIGxpa2VsaWhvb2QgZnVuY3Rpb24iLCBmaWcuYWxpZ249ImNlbnRlciJ9CmxpYnJhcnkocGxvdGx5KQoKYmV0YV8wIDwtIHNlcSgwLCAyLCBsZW5ndGgub3V0ID0gMTAwKQpiZXRhXzEgPC0gc2VxKC0wLjQsIC0wLjIsIGxlbmd0aC5vdXQgPSAxMDApCm9wdHMgPC0gZXhwYW5kLmdyaWQoYmV0YV8wLCBiZXRhXzEpCm9wdHMkbG9nbGlrIDwtIGFwcGx5KG9wdHMsIDEsIGZ1bmN0aW9uKHgpIG1sRXN0aW1hdGUoeFsxXSwgeFsyXSkpCnogPC0gbWF0cml4KG9wdHMkbG9nbGlrLCBuY29sID0gbGVuZ3RoKGJldGFfMCksIGJ5cm93ID0gVFJVRSkKCnBsb3RfbHkoeCA9YmV0YV8xLCB5ID0gYmV0YV8wLCB6ID0geikgJT4lIAogIGFkZF9zdXJmYWNlKCkgJT4lCiAgbGF5b3V0KHNjZW5lID0gbGlzdCgKICAgICAgICAgIHhheGlzID0gbGlzdCh0aXRsZSA9ICJiZXRhXzEiKSwKICAgICAgICAgIHlheGlzID0gbGlzdCh0aXRsZSA9ICJiZXRhXzAiKSwKICAgICAgICAgIHpheGlzID0gbGlzdCh0aXRsZSA9ICJMb2cgbGlrZWxpaG9vZCIpCiAgICApKQpgYGAKCkFzIHlvdSBjYW4gc2VlLCB0aGUgbWF4aW11bSBvZiB0aGUgbG9nIGxpa2VsaWhvb2QgZnVuY3Rpb24gbGllcyBhcm91bmQgYGBgLTAuMywgMWBgYCwgdGhlIHRydWUgcGFyYW1ldGVyIHZhbHVlcy4gTm93IHdlIG5lZWQgdG8gZmluZCBhbiBhbGdvcml0aG0gdGhhdCBmaW5kcyB0aGUgY29tYmluYXRpb24gb2YgJFxiZXRhXzAkIGFuZCAkXGJldGFfMSQgdGhhdCBvcHRpbWl6ZXMgdGhpcyBmdW5jdGlvbi4gVGhlcmUgYXJlIG11bHRpcGxlIHdheXMgdG8gZ28gYWJvdXQgdGhpcy4gVGhlIGBgYGdsbSgpYGBgIGZ1bmN0aW9uIHVzZXMgdGhlIGJ1aWx0LWluIG9wdGltaXphdGlvbiBmdW5jdGlvbiBgYGBvcHRpbSgpYGBgLiBXaGlsZSB3ZSBjb3VsZCBkbyB0aGUgc2FtZSwgd2Ugd2lsbCB1c2UgYSBzbGlnaHRseSBkaWZmZXJlbnQgYXBwcm9hY2ggdG8gbWFrZSB0aGUgcHJvY2VzcyBtb3JlIGludHVpdGl2ZS4gV2UgYXJlIGdvaW5nIHRvIGVtcGxveSBzb21ldGhpbmcgY2FsbGVkIF9ncmlkIG1heGltaXphdGlvbl8uIEJhc2ljYWxseSwgd2UgbWFrZSBhIGxpc3Qgb2YgYWxsIHBsYXVzaWJsZSBjb21iaW5hdGlvbnMgb2YgcGFyYW1ldGVyIHZhbHVlcyBhbmQgY2FsY3VsYXRlIHRoZSBsb2cgbGlrZWxpaG9vZCBmb3IgZWFjaCBjb21iaW5hdGlvbi4gVGhlbiB3ZSBzaW1wbHkgc2VsZWN0IHRoZSBwYXJhbWV0ZXIgY29tYmluYXRpb24gdGhhdCBoYXMgdGhlIGhpZ2hlc3QgbG9nIGxpa2VsaWhvb2QuCgpgYGBwcm9iX2JldGFfMGBgYCBhbmQgYGBgcHJvYl9iZXRhXzFgYGAgYXJlIG5vdyB2ZWN0b3JzIHRoYXQgY29udGFpbiAxMDAgcGxhdXNpYmxlIHZhbHVlcyBmb3IgZWFjaCBwYXJhbWV0ZXIuCmBgYHtyLCBtZXNzYWdlID0gRkFMU0UsIHdhcm5pbmcgPSBGQUxTRX0KcHJvYl9iZXRhXzAgPC0gc2VxKDAuNSwgMS41LCBsZW5ndGgub3V0ID0gMTAwKQpwcm9iX2JldGFfMSA8LSBzZXEoLTEsIDAsIGxlbmd0aC5vdXQgPSAxMDApCgojIFByaW50IG9uZSB2ZWN0b3IgYXMgYW4gZXhhbXBsZQpwcm9iX2JldGFfMApgYGAKCk5leHQgd2UgY3JlYXRlIGEgZGF0YSBmcmFtZSB0aGF0IGNvbnRhaW5zIGFsbCBwb3NzaWJsZSBjb21iaW5hdGlvbnMgb2YgYGBgcHJvYl9iZXRhXzBgYGAgYW5kIGBgYHByb2JfYmV0YV8xYGBgLiBUaGUgYGBgZXhwYW5kLmdyaWQoKWBgYCBmdW5jdGlvbiBkb2VzIGV4YWN0bHkgdGhhdC4gCgpgYGB7ciwgbWVzc2FnZSA9IEZBTFNFLCB3YXJuaW5nID0gRkFMU0V9CnBhcmFtcyA8LSBleHBhbmQuZ3JpZChwcm9iX2JldGFfMCwgcHJvYl9iZXRhXzEpCgojIFByaW50IGRmCnBhcmFtcwpgYGAKCldpdGggdGhlIGBgYGFwcGx5KClgYGAgZnVuY3Rpb24gd2UgY2FuIGNhbGN1bGF0ZSB0aGUgbG9nIGxpa2VsaWhvb2QgZm9yIGVhY2ggdmFsdWUgaW4gdGhlIGRhdGEgZnJhbWUuIE5vdGUgdGhhdCB0aGUgYGBgcGFyYW1zYGBgIGRhdGEgZnJhbWUgbm93IGhhcyBhIG5vdyBjb2x1bW4gY29udGFpbmluZyB0aGUgbG9nIGxpa2VsaWhvb2QuCgpgYGB7ciwgbWVzc2FnZSA9IEZBTFNFLCB3YXJuaW5nID0gRkFMU0V9CnBhcmFtcyRsb2dsaWsgPC0gYXBwbHkocGFyYW1zLCAxLCBmdW5jdGlvbih4KSBtbEVzdGltYXRlKHhbMV0sIHhbMl0pKQoKIyBwcmludCBkZgpwYXJhbXMKYGBgCgpOZXh0IHdlIHNpbXBseSBmaW5kIHRoZSBoaWdoZXN0IGxvZyBsaWtlbGlob29kIHZhbHVlIGFuZCB0aGUgYXNzb2NpYXRlZCBwYXJhbWV0ZXIgdmFsdWVzLgoKYGBge3IsIG1lc3NhZ2UgPSBGQUxTRSwgd2FybmluZyA9IEZBTFNFfQptYXhMaWsgPC0gd2hpY2gubWF4KHBhcmFtcyRsb2dsaWspCnBhcmFtc1ttYXhMaWssIF0KYGBgCgpBcyB5b3UgY2FuIHNlZSwgb3VyIG1ldGhvZCBjb21lcyBwcmV0dHkgY2xvc2UgdG8gdGhlIHRydWUgcGFyYW1ldGVyIHZhbHVlcy4gRm9yIGNvbXBhcmlzb24sIGhlcmUgaXMgdGhlIHNhbWUgbW9kZWwgY2FsY3VsYXRlZCB3aXRoIHRoZSBgYGBnbG0oKWBgYCBmdW5jdGlvbi4KCgpgYGB7ciwgbWVzc2FnZSA9IEZBTFNFLCB3YXJuaW5nID0gRkFMU0V9CnN1bW1hcnkoZ2xtKHNraXBwZWQgfiByYXRpbmdHZW5yZSwgZmFtaWx5ID0gYmlub21pYWwobGluayA9ICdsb2dpdCcpKSkKCmBgYAoKIyMjIyMgU3VtIG9mIExOIHZzIFByb2R1Y3QKClRvIGlsbHVzdHJhdGUgd2h5IHRoZSBuYXR1cmFsIGxvZyAobG4pIGlzIGltcG9ydGFudCBmb3IgY29tcHV0YXRpb25zIHdpdGggbnVtYmVycyBjbG9zZSB0byB6ZXJvIChzdWNoIGFzIGpvaW50IHByb2JhYmlsaXRpZXMpLCB3ZSBjcmVhdGUgYSB2ZWN0b3Igb2YgZmljdGl0aW91cyBwcm9iYWJpbGl0aWVzIGFuZCBtdWx0aXBseSB0aGVtIHdpdGggZWFjaCBvdGhlci4gQXMgd2UgY2FuIHNlZSwgYWxyZWFkeSBhIHNtYWxsIG51bWJlciBvZiB2YWx1ZXMgY2xvc2UgdG8gMCB3aWxsIGxlYWQgdG8gdGhlaXIgcHJvZHVjdCBiZWluZyBlcnJvbmVvdXNseSBpbnRlcnByZXRlZCBhcyBiZWluZyAwLiBJZiB3ZSBhcmUgb25seSBpbnRlcmVzdGVkIGluIGNvbXBhcmluZyBtYWduaXR1ZGUgKGFzIGluIHRoZSBjYXNlIG9mIGxpa2VsaWhvb2RzKSB3ZSBjYW4gc2FmZWx5IGFwcGx5IHRoZSBsbiwgc2luY2UgaXQgaXMgYSBtb25vdG9uaWNhbGx5IGluY3JlYXNpbmcgZnVuY3Rpb24gYW5kIHdpbGwgdGh1cyBub3QgY2hhbmdlIHRoZSByYW5raW5nLiAKYGBge3IsIG1lc3NhZ2UgPSBGQUxTRSwgd2FybmluZyA9IEZBTFNFfQpwcm9icyA8LSBjKDAuMDAwMDAxLCAwLjAwMDAwMSwgMC4wMDAwMDEsIDAuMDAwMDAxLCAwLjAwMDAwMSwgMC4wMDAwMDEsIDAuMDAwMDAxLAogICAgICAgICAgIDAuMDAwMDAxLCAwLjAwMDAwMSwgMC4wMDAwMDEsIDAuMDAwMDAxLCAwLjAwMDAwMSwgMC4wMDAwMDEsIDAuMDAwMDAxLAogICAgICAgICAgIDAuMDAwMDAxLCAwLjAwMDAwMSwgMC4wMDAwMDEsIDAuMDAwMDAxLCAwLjAwMDAwMSwgMC4wMDAwMDEsIDAuMDAwMDAxLAogICAgICAgICAgIDAuMDAwMDAxLCAwLjAwMDAwMSwgMC4wMDAwMDEsIDAuMDAwMDAxLCAwLjAwMDAwMSwgMC4wMDAwMDEsIDAuMDAwMDAxLAogICAgICAgICAgIDAuMDAwMDAxLCAwLjAwMDAwMSwgMC4wMDAwMDEsIDAuMDAwMDAxLCAwLjAwMDAwMSwgMC4wMDAwMDEsIDAuMDAwMDAxLAogICAgICAgICAgIDAuMDAwMDAxLCAwLjAwMDAwMSwgMC4wMDAwMDEsIDAuMDAwMDAxLCAwLjAwMDAwMSwgMC4wMDAwMDEsIDAuMDAwMDAxLAogICAgICAgICAgIDAuMDAwMDAxLCAwLjAwMDAwMSwgMC4wMDAwMDEsIDAuMDAwMDAxLCAwLjAwMDAwMSwgMC4wMDAwMDEsIDAuMDAwMDAxLAogICAgICAgICAgIDAuMDAwMDAxLCAwLjAwMDAwMSwgMC4wMDAwMDEsIDAuMDAwMDAxLCAwLjAwMDAwMSwgMC4wMDAwMDEsIDAuMDAwMDAxKQpwcm9kKHByb2JzKQoKbFByb2JzIDwtIGxvZyhwcm9icykgIyB0aGlzIGlzIHRoZSBsbgpzdW0obFByb2JzKQoKcHJvYnMyIDwtIHJiaW5kKHByb2JzLCBwcm9icywgcHJvYnMsIHByb2JzLCBwcm9icywKICAgICAgICAgICAgICAgIHByb2JzLCBwcm9icywgcHJvYnMsIHByb2JzLCBwcm9icykgIyBub3cgMTAgdGltZXMgYXMgbWFueSB2YWx1ZXMKbFByb2JzMiA8LSBsb2cocHJvYnMyKQpzdW0obFByb2JzMikKYGBgCgo=